package solution.design;

/**
 * @author zhangmin
 * @create 2021-10-21 13:17
 * 设计问题--二叉堆的应用--优先队列
 */
public class maxPQ <Key extends Comparable<Key>> {
//Java 的泛型，Key 可以是任何一种可比较大小的数据类型，比如 Integer 等类型
    //存储元素的数组
    private Key[] pq;
    //当前优先队列的元素个数
    private int N=0;

    public maxPQ(int cap){
        pq=(Key[]) new Comparable[cap+1];
    }
    /*返回队列中的最大元素*/
    public Key max(){
        return pq[1];
    }
    /* 插入元素 e
    * insert 方法先把要插入的元素添加到堆底的最后，然后让其上浮到正确位置。*/
    public void insert(Key e) {
        N++;
        pq[N]=e;
        swim(N);
    }

    /* 删除并返回当前队列中最大元素
    * delMax 方法先把堆顶元素 A 和堆底最后的元素 B 对调，然后删除 A，最后让 B 下沉到正确位置。*/
    public Key delMax() {
        Key max=pq[1];
        // 把这个最大元素换到最后，删除之
        exch(1,N);
        pq[N]=null;
        N--;
        sink(1);
        return max;
    }

    /* 上浮第 k 个元素，以维护最大堆性质 */
    private void swim(int k) {
        //如果上浮到顶层，就不能再上了
        while (k>1&&less(parent(k),k)){
            //k比k的上一层大，需要上浮换上去
            exch(parent(k),k);
            k=parent(k);
        }
    }

    /* 下沉第 k 个元素，以维护最大堆性质 */
    private void sink(int k) {
        // 如果沉到堆底，就沉不下去了
        while (left(k)<=N){
            int older=left(k);
            if (right(k)<=N&&less(older,right(k))){
                older=right(k);
            }
            // 结点 k 比俩孩子都大，就不必下沉了
            if (less(older,k)) break;
            // 否则，不符合最大堆的结构，下沉 k 结点
            exch(k,older);
            k=older;
        }
    }

    /*交换数组两个元素*/
    private  void exch(int i,int j){
        Key t=pq[i];
        pq[i]=pq[j];
        pq[j]=t;
    }
    /* pq[i] 是否比 pq[j] 小？ */
    private boolean less(int i,int j){
        return pq[i].compareTo(pq[j])<0;
    }

    // 父节点的索引
    int parent(int root) {
        return root / 2;
    }
    // 左孩子的索引
    int left(int root) {
        return root * 2;
    }
    // 右孩子的索引
    int right(int root) {
        return root * 2 + 1;
    }

}
